package string;

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * 示例 1：
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Auther Jun jie Yi
 * @Date 20:05 2022/1/10
 */
public class LeetCode5 {
    public static void main(String[] args) {
        System.out.println(longestPalindrome1("aaaab"));
    }

    //找出最长的回文字符串
    public static String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        String max = "", temp;
        char[] arr = s.toCharArray();
        //单个元素或者多个元素(多个元素为重复)
        int i = 0;
        while (i < arr.length) {
            int l = i - 1;
            int r = i + 1;
            //往右边遍历相同的
            while (r < arr.length) {
                if (arr[r] == arr[r - 1]) {
                    r++;
                } else {
                    break;
                }
            }
            //跳跃
            if (r > i + 1) {
                i = r;
            } else {
                i++;
            }
            if (l < 0) {
                temp = s.substring(0, r);
            } else {
                //首尾比较
                while (l >= 0 && r < arr.length) {
                    if (arr[l] == arr[r]) {
                        l--;
                        r++;
                    } else {
                        break;
                    }
                }
                temp = s.substring(l + 1, r);
            }
            if (temp.length() > max.length()) {
                max = temp;
            }
        }
        return max;
    }

    //找出最长的回文字符串
    public static String longestPalindrome1(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
//         保存起始位置，测试了用数组似乎能比全局变量稍快一点
        int[] range = new int[2];
        char[] str = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
//             把回文看成中间的部分全是同一字符，左右部分相对称
//             找到下一个与当前字符不同的字符
            i = findLongest(str, i, range);
        }
        return s.substring(range[0], range[1] + 1);
    }

    public static int findLongest(char[] str, int low, int[] range) {
//         查找中间部分
        int high = low;
        while (high < str.length - 1 && str[high + 1] == str[low]) {
            high++;
        }
//         定位中间部分的最后一个字符
        int ans = high;
//         从中间向左右扩散
        while (low > 0 && high < str.length - 1 && str[low - 1] == str[high + 1]) {
            low--;
            high++;
        }
//         记录最大长度
        if (high - low > range[1] - range[0]) {
            range[0] = low;
            range[1] = high;
        }
        return ans;
    }
}
